package com.zhangxiaofanfan.hotcode.fourth.third;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/rotting-oranges/?envType=study-plan-v2&envId=top-100-liked">994. 腐烂的橘子</a>
 *
 * @author zhangxiaofanfan
 * @date 2024-06-26 20:33:33
 */
public class HotCode052 {
    public static void main(String[] args) {
        int[][] grid = {
                {2, 1, 1},
                {1, 1, 0},
                {0, 1, 1}
        };
        // int[][] grid = {{0,2}};
        HotCode052 hotCode = new HotCode052();
        System.out.println(hotCode.orangesRotting(grid));
    }

    public int orangesRotting(int[][] grid) {
        int row = grid.length, col = grid[0].length, rowIndex, colIndex;
        Deque<Integer> queueRot = new ArrayDeque<>();
        int freshCount = 0;
        for (rowIndex = 0; rowIndex < row; rowIndex++) {
            for (colIndex = 0; colIndex < col; colIndex++) {
                if (grid[rowIndex][colIndex] == 1) {
                    freshCount++;
                } else if (grid[rowIndex][colIndex] == 2) {
                    queueRot.add(rowIndex * col + colIndex);
                }
            }
        }
        int minute = 0;
        while (!queueRot.isEmpty()) {
            int count = queueRot.size();
            int rot = 0;

            for (int i = 0; i < count; i++) {
                int first = queueRot.removeFirst();
                rowIndex = first / col;
                colIndex = first % col;
                if (rowIndex - 1 >= 0 && grid[rowIndex - 1][colIndex] == 1) {
                    freshCount--;
                    queueRot.add(first - col);
                    grid[rowIndex - 1][colIndex] = 2;
                    rot++;
                }
                if (rowIndex + 1 < row && grid[rowIndex + 1][colIndex] == 1) {
                    freshCount--;
                    queueRot.add(first + col);
                    grid[rowIndex + 1][colIndex] = 2;
                    rot++;
                }
                if (colIndex - 1 >= 0 && grid[rowIndex][colIndex - 1] == 1) {
                    freshCount--;
                    queueRot.add(first - 1);
                    grid[rowIndex][colIndex - 1] = 2;
                    rot++;
                }
                if (colIndex + 1 < col && grid[rowIndex][colIndex + 1] == 1) {
                    freshCount--;
                    queueRot.add(first + 1);
                    grid[rowIndex][colIndex + 1] = 2;
                    rot++;
                }
            }
            minute += (rot == 0 ? 0 : 1);
        }
        return freshCount == 0 ? minute : -1;
    }
}
